package basic_1025;

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner scanner=new Scanner(System.in);
		
		int N=scanner.nextInt();
		
		int[] originalNumber=new int[N];
		int[] progressNumber=new int[N];
		
		for(int i=0;i<N;i++) {
			originalNumber[i]=scanner.nextInt();
		}
		
		for(int i=0;i<N;i++) {
			progressNumber[i]=scanner.nextInt();
		}
		
		scanner.close();
		
		boolean isInsertion=false;
		
		int[] progress=copy(originalNumber);
		for(int i=1;i<N;i++) {
			progress=InsertionProgress(progress, i);
			if(isInsertion) {
				if(progress_equal(progress, progressNumber)) {
					continue;
				}
				break;
			}
			if(progress_equal(progress, progressNumber)) {
				isInsertion=true;
			}
		}
		
		if(isInsertion) {
			System.out.println("Insertion Sort");
			System.out.println(toString(progress));
			return;
		}
		
		progress=copy(originalNumber);
		
		boolean isMerge=false;
		for(int times=1;times<=Math.sqrt(N-1)+1;times++) {
			progress=MergeProgress(progress, times);

			if(isMerge) {
				break;
			}
			if(progress_equal(progress, progressNumber)) {
				isMerge=true;
			}
		}
		if(isMerge) {
			System.out.println("Merge Sort");
			
			System.out.println(toString(progress));
		}
	
	}
	
	static int[] copy(int[]numbers) {
		int[] back=new int[numbers.length];
		for(int i=0;i<numbers.length;i++) {
			back[i]=numbers[i];
		}
		return back;
	}
	
	static String toString(int[]numbers) {
		String out="";
		for(int i:numbers) {
			out+=i+" ";
		}
		return out.trim();
	}
	
	static int[] InsertionProgress(int[]lastProgress,int position) {
		int[]progress=lastProgress;
		
		int num=progress[position];
		for(int i=position;i>=0;i--) {
			if(i==0||num>=progress[i-1]) {
				progress[i]=num;
				break;
			}else {
				progress[i]=progress[i-1];
			}
		}
		return progress;
	}
	
	static int[] MergeProgress(int[]lastProgress,int times) {
		int[]progress=lastProgress;
		
		int groupLength=(int)Math.pow(2, times);
		int groupNumber=(lastProgress.length-1)/groupLength+1;
		
		for(int i=0;i<groupNumber;i++) {
			int length=groupLength;
			if(i==groupNumber-1) {
				length=lastProgress.length-groupLength*(groupNumber-1);
			}
			int[] group=new int[length];
			for(int j=0;j<length;j++) {
				group[j]=lastProgress[i*groupLength+j];
			}
			
			for(int j=1;j<length;j++) {
				group=InsertionProgress(group, j);
			}
			
			for(int j=0;j<length;j++) {
				progress[i*groupLength+j]=group[j];
			}
		}
		
		return progress;
	}
	
	static boolean progress_equal(int[]progress1,int[]progress2) {
		if(progress1.length!=progress2.length) {
			return false;
		}
		
		for(int i=0;i<progress1.length;i++) {
			if(progress1[i]!=progress2[i]) {
				return false;
			}
		}
		
		return true;
	}
	
}
